﻿namespace Learn.Service
{
    public class LeetcodeService
    {
        #region 哈希
        public static int[] TwoSum(int[] nums, int target)
        {
            int n = nums.Length;
            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    if (nums[i] + nums[j] == target)
                        return [i, j];
                }
            }
            return [];
        }


        public static int[] TwoSumDic(int[] nums, int target)
        {
            Dictionary<int, int> dic = [];
            for (int i = 0; i < nums.Length; i++)
            {
                if (dic.ContainsKey(target - nums[i]))
                    return [dic[target - nums[i]], i];
                dic.TryAdd(nums[i], i);
            }
            return [];
        }


        public static IList<IList<string>> GroupAnagrams(string[] strs)
        {
            IList<IList<string>> res = [];
            var dic = new Dictionary<string, IList<string>>();
            foreach (var item in strs)
            {
                char[] cs = item.ToCharArray();
                Array.Sort(cs);
                string key = string.Join("", cs);
                if (dic.ContainsKey(key))
                    dic[key].Add(item);
                else
                    dic[key] = [item];
            }
            foreach (var key in dic.Keys)
            {
                res.Add(dic[key]);
            }

            return res;
        }


        public static int LongestConsecutive(int[] nums)
        {
            if (nums == null || nums.Length <= 0) return 0;
            var l = nums.ToList();
            l.Sort();//排序
            int longestStreak = 0;
            int currentStreak = 1;
            for (int i = 0; i < nums.Length - 1; i++)
            {
                //连续跳过计数
                if (l[i] == l[i + 1])
                    continue;
                //连续累计
                if (l[i] + 1 == l[i + 1])
                    currentStreak++;
                //中断连续时，当前计数重新，并把最长赋值返回结果
                else
                {
                    longestStreak = Math.Max(longestStreak, currentStreak);
                    currentStreak = 1;
                }
            }
            //longestStreak记录上次最大长度，currentStreak当前长度，获取最大的返回
            return Math.Max(longestStreak, currentStreak);
        }
        #endregion

        #region 双指针

        public static void MoveZeroes(int[] nums)
        {
            //List<int> zeroes = [];
            //List<int> ints = [];
            //foreach (var item in nums)
            //{
            //    if (item == 0)
            //        zeroes.Add(0);
            //    else
            //        ints.Add(item);
            //}
            //nums = new int[nums.Length];
            //ints.Sort();
            //ints.CopyTo(nums, 0);
            //zeroes.CopyTo(nums, ints.Count);
            //return JsonConvert.SerializeObject(nums);
            // 使用双指针方法，一次遍历数组
            int left = 0;
            // 遍历整个数组
            for (int right = 0; right < nums.Length; right++)
            {
                // 如果当前元素不是0
                if (nums[right] != 0)
                {
                    // 交换当前元素和左指针指向的元素
                    //int temp = nums[right];
                    //nums[right] = nums[left];
                    //nums[left] = temp;
                    // 交换当前元素和左指针指向的元素
                    //(nums[left], nums[right]) = (nums[right], nums[left]);
                    // 左指针右移
                    left++;
                }
            }

            // 第一次遍历，使用 j 指针记录非零元素的个数
            // 只要是非零元素，就将其赋给 nums[j]
            int j = 0;
            for (int i = 0; i < nums.Length; ++i)
            {
                if (nums[i] != 0)
                {
                    nums[j++] = nums[i];
                }
            }

            // 非零元素统计完了，剩下的元素都是零
            // 第二次遍历，将数组末尾的元素都赋值为零
            for (int i = j; i < nums.Length; ++i)
            {
                nums[i] = 0;
            }

        }


        public static int MaxArea(int[] height)
        {
            //int maxArea = 0;
            //int total = height.Length;
            //for (int i = 0; i < total - 1; i++)
            //{
            //    for (int j = i + 1; j < total; j++)
            //    {
            //        int area = (j - i) * Math.Min(height[i], height[j]);
            //        maxArea = Math.Max(maxArea, area);
            //    }
            //}
            //return maxArea;

            int i = 0, j = height.Length - 1, max = 0;
            while (i < j)
            {
                max = height[i] < height[j] ?
                    Math.Max(max, (j - i) * height[i++]) :
                    Math.Max(max, (j - i) * height[j--]);
            }
            return max;

        }


        public static IList<IList<int>> ThreeSum(int[] nums)
        {
            //IList<IList<int>> res = [];
            //int total = nums.Length;
            //var dic = new List<string>();
            //for (int x = 0; x < total - 2; x++)
            //{
            //    for (int y = x + 1; y < total - 1; y++)
            //    {
            //        for (int z = y + 1; z < total; z++)
            //        {
            //            if (nums[x] + nums[y] + nums[z] == 0)
            //            {
            //                List<int> keys = [nums[x], nums[y], nums[z]];
            //                keys.Sort();
            //                string key = string.Join("", keys);
            //                if (dic.Contains(key))
            //                {
            //                    continue;
            //                }
            //                dic.Add(key);
            //                //dic.Add(key, [nums[x], nums[y], nums[z]]);
            //                res.Add(keys);
            //            }

            //        }
            //    }

            //}

            IList<IList<int>> res = [];
            int len = nums.Length;
            Array.Sort(nums);
            for (int k = 0; k < len - 2; k++)
            {
                if (nums[k] > 0) break;
                if (k > 0 && nums[k] == nums[k - 1]) continue;
                int i = k + 1, j = len - 1;
                while (i < j)
                {
                    int sum = nums[k] + nums[i] + nums[j];
                    if (sum < 0)
                    {
                        while (i < j && nums[i] == nums[++i]) ;
                    }
                    else if (sum > 0)
                    {
                        while (i < j && nums[j] == nums[--j]) ;
                    }
                    else
                    {
                        res.Add([nums[k], nums[i], nums[j]]);
                        while (i < j && nums[i] == nums[++i]) ;
                        while (i < j && nums[j] == nums[--j]) ;
                    }
                }
            }
            return res;

        }

        public static int LengthOfLongestSubstring(string s)
        {
            List<char> ls = [];
            int n = s.Length;
            int intMaxLength = 0;

            for (int i = 0; i < n; i++)
            {
                if (ls.Contains(s[i]))
                {
                    ls.RemoveRange(0, ls.IndexOf(s[i]) + 1);
                }
                ls.Add(s[i]);
                intMaxLength = Math.Max(intMaxLength, ls.Count);
            }

            return intMaxLength;

        }


        public static IList<int> FindAnagrams(string s, string p)
        {
            //s = "cbaebabacd";
            //p = "abc";
            if (s.Length == 0) return [];
            int[] arrW = new int[26]; //滑动窗口数组
            int[] arrP = new int[26]; // 字符串 P 的字符统计数组
            foreach (char c in p.ToCharArray())
                arrP[c - 'a']++; // 将 p 映射到数组中
            IList<int> res = [];
            int left = 0, right = 0;
            while (right < s.Length)
            {
                char cr = s[right]; // 窗口右边字符
                right++;
                arrW[cr - 'a']++;
                while (arrW[cr - 'a'] > arrP[cr - 'a'])
                {
                    //窗口内出现个数大于 P 中的，调整窗口
                    char cl = s[left];
                    arrW[cl - 'a']--;
                    left++;
                }
                if (right - left == p.Length)
                    res.Add(left);
            }
            return res;

            //var res = new List<int>();
            //// 若s长度小于p，s中必然没有p的异位词
            //if (s.Length < p.Length)
            //    return res;
            //int[] charCnt = new int[26];
            //// 记录各字符在p长度下出现情况，s对应字符累加，p对应字符递减
            //for (int i = 0; i < p.Length; i++)
            //{
            //    charCnt[s[i] - 'a']++;
            //    charCnt[p[i] - 'a']--;
            //}
            //var diff = 0;
            //// 遍历字符累计数组，各字符绝对值之和就是两者的差异
            //for (int i = 0; i < 26; i++)
            //{
            //    diff += Math.Abs(charCnt[i]);
            //}
            //// 无差异直接添加
            //if (diff == 0)
            //    res.Add("0");
            //// 从p长度开始，遍历s字符串
            //for (int i = p.Length; i < s.Length; i++)
            //{
            //    // 进窗口的字符索引
            //    var enCharVal = s[i] - 'a';
            //    // 当原有值小于0，进入滑动窗口，只会减少差异
            //    if (charCnt[enCharVal] < 0)
            //        diff--;
            //    // 反则增加差异
            //    else
            //        diff++;
            //    charCnt[enCharVal]++;
            //    // 出窗口的字符索引
            //    var deCharVal = s[i - p.Length] - 'a';
            //    // 当原有值大于0，退出滑动窗口，只会减少差异
            //    if (charCnt[deCharVal] > 0)
            //        diff--;
            //    // 反则增加差异
            //    else
            //        diff++;
            //    charCnt[deCharVal]--;
            //    // 无差异直接添加
            //    if (diff == 0)
            //        res.Add(i - p.Length + 1);
            //}
            //return res;

        }


        public static int Trap(int[] height)
        {
            int left = 0, right = height.Length - 1;
            int ans = 0;
            int left_max = 0, right_max = 0;
            while (left < right)
            {
                if (height[left] < height[right])
                {
                    if (height[left] >= left_max)
                    {
                        left_max = height[left];
                    }
                    else
                    {
                        ans += (left_max - height[left]);
                    }
                    ++left;
                }
                else
                {
                    if (height[right] >= right_max)
                    {
                        right_max = height[right];
                    }
                    else
                    {
                        ans += (right_max - height[right]);
                    }
                    --right;
                }
            }
            return ans;
        }

        public static int SingleNumber(int[] nums)
        {
            //Dictionary<int, int> dict = new Dictionary<int, int>();
            //foreach (int num in nums)
            //{
            //    if (dict.ContainsKey(num))
            //    {
            //        dict[num]++;
            //    }
            //    else
            //    {
            //        dict.Add(num, 1);
            //    }
            //}
            //foreach (KeyValuePair<int, int> pair in dict)
            //{
            //    if (pair.Value == 1)
            //    {
            //        return pair.Key;
            //    }
            //}
            //return -1;
            int result = 0;
            foreach (var num in nums)
            {
                var r = Convert.ToString(result, 2).PadLeft(8, '0');
                var n = Convert.ToString(num, 2).PadLeft(8, '0');
                result = result ^ num;
            }
            return result;
        }


        public static bool IsValid(string s)
        {
            Dictionary<char, char> dict = new()
            {
                { ')', '(' },
                { '}', '{' },
                { ']', '[' }
            };

            Stack<char> stack = new();

            foreach (char c in s)
            {
                if (dict.ContainsKey(c))
                {
                    if (stack.Count == 0 || stack.Peek() != dict[c])
                    {
                        return false;
                    }
                    stack.Pop();
                }
                else
                {
                    stack.Push(c);
                }
            }

            return stack.Count == 0;
        }


        public static int SearchInsert(int[] nums, int target)
        {
            int left = 0, right = nums.Length - 1, mid;
            while (left <= right)
            {
                mid = left + (right - left) / 2;
                if (nums[mid] == target)
                {
                    return mid;
                }
                else if (nums[mid] < target)
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
            return left; // 目标值不存在，返回应该插入的位置

        }


        public static ListNode MergeTwoLists(ListNode list1, ListNode list2)
        {
            //if (list1 == null) return list2;
            //if (list2 == null) return list1;
            //if (list1.val < list2.val)
            //{
            //    list1.next = MergeTwoLists(list1.next, list2);
            //    return list1;
            //}
            //else
            //{
            //    list2.next = MergeTwoLists(list1, list2.next);
            //    return list2;
            //}

            ListNode dummy = new(-1), p = dummy;
            ListNode p1 = list1, p2 = list2;
            while (p1 != null && p2 != null)
            {
                if (p1.val > p2.val)
                {
                    p.next = p2;
                    p2 = p2.next;
                }
                else
                {
                    p.next = p1;
                    p1 = p1.next;
                }
                p = p.next;
            }
            if (p1 != null)
                p.next = p1;
            if (p2 != null)
                p.next = p2;
            return dummy.next;
        }

        #endregion

        public static IList<IList<int>> Generate(int numRows)
        {
            IList<IList<int>> triangle = [];
            for (int rowNumber = 1; rowNumber <= numRows; rowNumber++)
            {
                // 创建一个新行，并初始化第一个和最后一个元素为1
                List<int> row = new(new int[rowNumber])
                {
                    [0] = 1,
                    [rowNumber - 1] = 1
                };
                // 根据上一行计算中间的元素
                for (int j = 1; j < rowNumber - 1; j++)
                {
                    row[j] = triangle[rowNumber - 2][j - 1] + triangle[rowNumber - 2][j];
                }
                triangle.Add(row);
            }

            return triangle;
        }

        public static IList<int> InorderTraversal(TreeNode root)
        {
            IList<int> list = [];
            if (root == null) return list;
            Stack<TreeNode> stack = new();
            TreeNode cur = root;
            stack.Push(cur);
            while (stack.Count > 0)
            {
                if (cur.left != null)
                {
                    cur = cur.left;
                    stack.Push(cur);
                }
                else
                {
                    var node = stack.Pop();
                    list.Add(node.val);
                    if (node.right != null)
                    {
                        cur = node.right;
                        stack.Push(cur);
                    }
                }
            }
            return list;


        }


        public static int MajorityElement(int[] nums)
        {

            int amount = 0;
            int num = 0;
            foreach (var item in nums)
            {
                if (amount == 0)
                {
                    num = item;
                }
                if (num == item)
                {
                    amount += 1;
                }
                else
                {
                    amount -= 1;
                }
            }
            return num;

            //Dictionary<int, int> dic = [];
            //foreach (int num in nums)
            //{
            //    if (dic.ContainsKey(num))
            //    {
            //        dic[num]++;
            //    }
            //    else
            //    {
            //        dic.Add(num, 1);
            //    }
            //}
            //foreach (var keyValue in dic)
            //{
            //    if (keyValue.Value > nums.Length / 2)
            //    {
            //        return keyValue.Key;
            //    }
            //}
            //return 0;

        }

        public static ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            // 初始化哨兵节点和进位  
            ListNode dummy = new(0);
            ListNode current = dummy;
            int carry = 0;

            // 遍历两个链表  
            while (l1 != null || l2 != null)
            {
                int x = (l1 != null) ? l1.val : 0;
                int y = (l2 != null) ? l2.val : 0;
                int sum = carry + x + y;

                // 创建新节点存储当前位的和  
                current.next = new ListNode(sum % 10);
                current = current.next;

                // 更新进位  
                carry = sum / 10;

                // 移动链表指针  
                if (l1 != null) l1 = l1?.next ?? new();
                if (l2 != null) l2 = l2?.next ?? new();
            }

            // 如果最后还有进位，则添加一个新节点  
            if (carry > 0)
            {
                current.next = new ListNode(carry);
            }

            // 返回哨兵节点的下一个节点，即结果链表的头节点  
            return dummy?.next ?? new();
        }



    }

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
    public class ListNode(int val = 0, ListNode? next = null)
    {
        public int val = val;
        public ListNode? next = next;
    }

    public class TreeNode()
    {
        public int val;
        public TreeNode? left;
        public TreeNode? right;
    
    }

}
